Steady advances in miniaturization techniques for integrated circuits have resulted in circuit devices, particularly transistors, of ever-diminishing sizes. Generally speaking, each generation of an integrated circuit utilizes transistors that occupy smaller footprints on the semiconductor substrate than those of the previous generation. However, consumer desires, with resultant design demands, seem to grow even faster than integrated circuit devices have been shrinking. As a result, rather than being in surplus, real estate on the circuit substrate remains at a premium. Every unit of area on a substrate must be maximally utilized to squeeze as much performance as possible into the limited space of the circuit die. If a way can be found to reduce the size of a circuit in one portion of a chip, the area thereby freed up can be used to support additional circuitry to pack even more logic functionality into the same die. The miniaturization race therefore involves not only reducing the footprint of individual devices, such as transistors, on the die, but also finding ways to use fewer such devices to achieve the same functionality.
Many digital designs employ read-only memory (ROM), which is built directly onto the same die with the rest of the circuit. This on-chip ROM provides necessary data for the circuit, such as microcode instructions, object code, operating parameters and the like. Generally, a ROM circuit has Q address lines as input for accessing 2Q data words respectively stored within the ROM at 2Q addresses, where Q≧1. Each data word may hold P data bits, P≧1, which are provided on P respective bit output lines. Hence, at a high level of abstraction, a ROM stores a dataset and implements a 2Q×P look-up table with this dataset, in which the input value is provided on the Q address lines, and the P-bit data word output result is provided on the P bit output lines. By way of example, the following 24×4 dataset is considered:
TABLE 1AddressData word(A3, A2, A1, A0)B1B1B2B30000 (0)00110001 (1)10010010 (2)11110011 (3)10110100 (4)00110101 (5)01010110 (6)11110111 (7)11011000 (8)00111001 (9)10011010 (10)00001011 (11)00001100 (12)00111101 (13)10111110 (14)10011111 (15)1101
Four address input bits, A0, A1, A2 and A3, provide sixteen addresses, 0 to 15, each of which stores a data word of four bits, B0, B1, B2 and B3. Although specific reference in the following is drawn to a 16×4 dataset, the principles are applicable to any generalized 2Q×P dataset, where Q is the number of address bits, and P is the number of bits in the data word.
A prior art design for a ROM 10 that implements the dataset of Table 1 is shown in FIG. 1. The prior art design 10 provides a four-bit output data word in response to receiving a four-bit input address. The ROM 10 comprises four bit lines B0, B1, B2 and B3 tied to ground via pull-down resistors 14, and sixteen word lines L0 to L15 connected to an address decoder 12. The word lines L0-L15 are normally held low by the address decoder 12. The decoder 12 is a Q to 2Q decoder. In the specific example, the decoder 12 accepts as input four address lines A0, A1, A2 and A3, and based upon this input selects, or asserts, one of the 24 word lines L0-L15. Since the ROM 10 uses true logic, when a word line L0-L15 is asserted, that word line L0-L15 goes high. The decoder 12 creates a one-to-one correspondence between input values provided by address lines A0-A3 and selected word lines L0-L15, wherein when an address “x” is placed upon address lines A0-A3, the decoder 12 asserts, or raises, word line Lx. For example, if the address inputs (A3, A2, A1, A0) are (0, 0, 0, 0), then the decoder 12 will assert word line L0; all other word lines L1-L15 are not asserted, and so remain low. Similarly, if the address inputs (A3, A2, A1, A0) are (1, 1, 1, 1), then the decoder 12 will assert word line L15, and all other word lines L0-L14 are not asserted. In the following, it is assumed that A3 is the high order address bit, and that A0 is the low order address bit.
Because each output bit line B0-B3 is tied to ground, the bit lines B0-B3 are normally in a logical zero state. By utilizing any suitable connecting device 16 to selectively electrically connect each output bit B0-B3 to zero or more word lines L0-L15, it is possible to implement the dataset of Table 1. By electrically connecting an output bit line B0-B3 to a word line L0-L15, the normally-low output bit line B0-B3 will go high when the word line L0-L15 is asserted. Each connecting device 16 may therefore represent a logical one for the corresponding output bit line B0-B3 at a corresponding value of the input address provided by address lines A0-A3.
For the sake of simplicity, the connecting device 16 of FIG. 1 is shown as a diode 16. One of skill in the art will readily recognize that this diode 16 may, in fact, be replaced by a transistor. Hence, one way to implement the logic array 18 is by using MOS transistors for the connecting devices 16, rather than diodes. It should be noted that when diodes are used as connecting devices 16, the bit lines B0-B3 are normally held low during the read operation, and a diode is typically electrically connected when the associated bit is supposed to be ‘1’. However, when MOS transistors are used, the bit lines B0-B3 are charged during the read cycle, and thus are normally held high instead of low. A MOS transistor is therefore used as the connecting device 16 for all those bits where the output is supposed to be ‘0’. But for this difference, the remainder of the logic and following discussion holds for both diode and transistor based configurations. Such minor variations in the type of logic used for the logic array 18 are well within the means of one having ordinary skill in the art, and in the following, for the sake of simplicity, only diodes are shown. One of reasonable skill in the art will also readily note that the ROM 10 can also be configured as a 2-D structure, with both column and row decoders. Such a 2-D structure is simply a slightly more complex generalization of the structure shown in FIG. 1, and is also known in the art.
Because ROM is such a ubiquitous component, it would be highly beneficial if a method could be found to reduce the footprint of the ROM, and thereby free up substrate real estate for other circuit components. In particular, since the logic array 18 that encodes the dataset occupies a relatively large footprint, it would be particularly beneficial if the size of the logic array 18 could be reduced.